/*
* 给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点，Node.left的任何后代的值 严格小于 Node.val,Node.right的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。
* 递归实现
https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/

* */
class BstFromPreorder {
    public int[] preorder;
    public int len;
    public int index;
    public TreeNode bstFromPreorder(int[] preorder) {
        this.preorder=preorder;
        this.len=preorder.length;
        return dfs(Integer.MIN_VALUE,Integer.MAX_VALUE);
    }
    public TreeNode dfs(int lower,int upper){
        if(index==len){
            return null;
        }
        int cur=preorder[index];
        if(cur<lower||cur>upper){
            return null;
        }
        index++;
        TreeNode root=new TreeNode(cur);
        root.left=dfs(lower,cur);
        root.right=dfs(cur,upper);
        return root;
    }
}